1. Field of the Invention
The invention described herein is related to determining an amount of noncompliant traffic in a communication network for purposes of detecting a denial-of-service (DoS) attack. More specifically, the present invention monitors the ratio of incoming and outgoing traffic of traffic flows in a communication network to identify flows not conforming to the network transmission protocol, which is an indication of a DoS attack.
2. Description of the Prior Art
Information is conveyed over the Internet via datagrams that are directed from a source to a destination through a number of routers. The traditional routers on the Internet do not maintain a traffic flow state of the flows (a traffic “flow” generally refers to a stream of data packets emanating from the same source node and bound for the same destination node and which are transported along the same path) traversing the device. Whereas, the Internet routing architecture has served the Internet community well in terms of its simplicity, its scalability and its heterogeneity, a stateless routing mechanism does not distinguish between packets belonging to legitimate traffic and packets transmitted for malicious purposes. Identifying malicious hosts or preventing malicious traffic within the Internet has proven to be very difficult.
Denial-of-service (DoS) attacks belong to a class of malicious traffic that aims to disrupt service provided to legitimate users by a server on the Internet. DoS attacks are generally classified into two different categories: protocol weakness attacks and resource exhaustion attacks. Protocol weakness attacks succeed by exploiting the weaknesses in the protocol/application design or implementation of the network. In resource exhaustion attacks, denial of service is achieved by overwhelming the resources required to service legitimate clients.
Internet protocol (IP) packets are permitted by the protocol to have a maximum size of 216-1 bytes. Due to fragmentation and reassembly of packets in the network layer, it is possible for a server to receive an IP packet that is larger than the maximum allowed size. If the server does not check the size of such a fragmented packet during its reassembly, then the server undergoes a buffer overflow during the reassembly process. The server fails and is unable to process any further service requests by legitimate clients. Such attacks are typically carried out by malicious hosts using Internet Control Message Protocol (ICMP) echo packets, or “ping” packets, and such an attack is thus referred to as the “ping of death”. Ping of death attacks are successful when the system under attack does not check the size of the packet during its reassembly and, as such, this attack is an example of a protocol weakness attack.
In a transmission control protocol (TCP) “SYN” attack, on the other hand, success is achieved only when an attacker is able to send a large number of synchronization requests through TCP SYN packets. During a TCP compliant connection procedure, a client sends a SYN packet to a server and the server responds with a SYN-ACK packet. At that time, the server allocates resources for the TCP connection. The client replies to the server's SYN-ACK with an ACK packet to complete the connection setup phase. This procedure is often referred to as the TCP “three-way handshake”.
If a server does not receive the expected ACK packet responsive to its SYN-ACK packet, it repeatedly resends the SYN-ACK packet and waits for the ACK packet at increasingly longer wait times between retransmissions. Meanwhile, the server's resources remain allocated in anticipation of a completed three-way handshake. Eventually, after a total wait time of three minutes, if the server still has not received the expected ACK packet from the client, it will free the allocated data structures and reset the connection. Due to the limited memory available for the TCP data structures, a server can service at most a fixed number of simultaneous connections. If an attacker sends numerous spoofed SYN packets, the memory available at the server will ultimately be exhausted and unable to accommodate new TCP connections. Consequently, the server will be unable to provide services to legitimate clients in that the communication session failed to be established. Such an attack is an example of a resource exhaustion attack since the attacker exhausts the memory resources at the server to prevent further TCP connection requests from being fulfilled. A SYN attack may also be considered an implementation weakness attack since the mechanism exploited for SYN attacks is a vulnerability of the TCP three-way handshake.
Bandwidth attacks, or flooding attacks, are executed by transmitting a large number of packets towards a victim. The communication links terminating at the victim become heavily congested and a significant portion of packets are dropped to relieve the congestion. Since the Internet routers are stateless and cannot distinguish between the legitimate packets and those packets that are part of the attack, both types of packets are dropped arbitrarily. The victim is consequently unable to service legitimate users trying to access its services. Bandwidth attacks are thus resource exhaustion type DoS attacks and may be performed using packets formatted as TCP packets, user datagram protocol (UDP) packets or some other IP packet.
Bandwidth attacks are a unique and important class of DoS attacks. First, the attackers are typically unwillingly-participating end hosts and the victims are typically server farms or enterprise commercial sites. The victims generally have more resources in terms of bandwidth and processing than the combined resources of a few individual end hosts. Hence, several attackers may participate in what is referred to as a distributed DoS (DDoS) attack. Additionally, because bandwidth attacks require a large number of attack packets to be successful, significant network resources are consumed along the entire attack path. Thus, the impact of a flooding attack is felt more widely in the Internet than other DoS attacks and large DDoS attacks result in global Internet instabilities. Finally, the large number of packets make defensive or corrective action at the victim very difficult.
The distributed nature of the attacks described above and the inability to distinguish attack packets from legitimate packets presents interesting and challenging technical problems. Due to the ease with which such attacks can be mounted and the extent of damage they cause, mitigating flooding attacks is an area of intense development and is critical to ensure stable functioning of the Internet.
For TCP compliant traffic, only a fraction of TCP bandwidth attack packets addressed to the victim reach their destination. The victim may respond to even fewer TCP packets because its resources in terms of processing and memory have been exhausted. A legitimate host attempting to communicate with the victim during the attack will perceive the network to be congested and will multiplicatively decrease its sending rate. Attackers, on the other hand, will ceaselessly send large numbers of packets to achieve the denial of service at the victim. Thus, the number of packets sent to the victim by the attackers greatly outnumber the number of response packets received by those attackers during the attack. If the source addresses of the attack packets are spoofed, respective response packets will not reach the attacking host and the ratio of attack packets to their corresponding response packets will be even larger at the attackers. This characteristic of TCP flooding attacks, and flooding attacks of other protocols, may be exploited as a detection device. However, such a detection mechanism must observe a flow's packets in both directions to correctly determine if the flow is legitimate. Otherwise, the system will erroneously report a legitimate flow as an attack.
Routing in the Internet is generally asymmetric, i.e., the path for packets of a flow in one direction is different than the path for packets flowing in the opposite direction. Hence, detection systems using packet ratios to detect attacks may be deployed only in stub networks, either at the source/attacker site of the flow (source domain detection) or at the destination/victim of a flow (victim domain detection). As used herein, a “stub” domain or network refers to a network having a predetermined network address space coupled to the Internet via a border gateway. A stub domain comprises an autonomous system (AS), i.e., a collection of IP networks and routers under the control of a single entity that presents a common routing policy to the Internet. For example, in the well-known border gateway protocol (BGP), each stub domain, or AS, has assigned thereto a unique AS number, or ASN, for use in BGP routing. The ASN thus uniquely identifies the stub domain on the Internet.
Several DoS detection and prevention mechanisms presently exist and are generally classified across many dimensions, such as deployment location, detection heuristic, type and level of infrastructure change, etc. Two of these approaches, known as MULTOPS and D-WARD, each use packet ratios on flows to detect attacks in stub domains. MULTOPS implements a router that maintains packet rate statistics for the traffic traversing the router using a 4-level 256-ary tree data structure, as is shown in FIG. 1. Each node 102, 104, 106, 108, 110, 112 in the data structure 120 corresponds to an IP prefix, as is shown in the Figure, where the position of the node determines the prefix it represents. For example, the third child of node 106 represents the prefix 4.2.*.*. Each node has 256 entries, each corresponding to one of the 256 children of the node. Each entry 125 includes three fields: an incoming packet count field, shown at 122, an outgoing packet count field, shown at 124, and a pointer to the child node, as shown at 126. Whenever a packet that maps to the entry, i.e., the packets address prefix, is the same as that of the entry, the entry's counter 122, 124 corresponding to the packets direction is updated. When a packet rate for a prefix reaches a certain threshold, the child node for the corresponding prefix is initialized. When the packet rate falls below a threshold, the node is contracted by deleting the node's children. In this manner, MULTOPS can be adapted through its data structure to track changing traffic characteristics of the stub domain as well as the resources available at the router implementing the MULTOPS scheme.
MULTOPS detects attacks using the ratio of outgoing and incoming packet rates for each prefix for which it maintains packet rate statistics. Whenever a node's outgoing-to-incoming packet rate ratio falls outside a predetermined range, the corresponding prefix is flagged and the packets from, or to, the prefix are dropped.
Among its shortcomings is that MULTOPS will miss reflector attacks if the attacker employs a large number of reflectors. In a reflector attack, the attacker sends packets to public servers (reflectors) throughout the Internet. These packets have the victim's address as the source address, i.e., the source addresses on the packets are spoofed with the victims address and are typically request packets, such as ICMP echo requests or TCP connection request packets, that generate a response from the servers. Since the source address for the request packets have the victim's address, all the response packets are sent to the victim. If the number of responses is high, the link corresponding to the victim's address will become congested. If the number of reflectors employed in the attack is high, the attack can be successful even if the number of request packets to each reflector is low. In such a case, MULTOPS will fail to track all of the individual flows to the reflectors and will be unable to detect the presence of the attack.
Another shortcoming of MULTOPS is that an attacker can exploit knowledge of legitimate flows to mask low-rate attack flows. For example, if flows to a.b.c.d and a.b.c.e are mapped to the same MULTOPS counter as an attack flow a.b.c.f and the rates of all three flows are low enough so that their combined rate will not result in a count that exceeds the threshold, the MULTOPS system will be unable to resolve the attack flow from the legitimate flows.
D-WARD is another source domain DoS detection system known in the art. D-WARD maintains a packet count at flow level, i.e., for each external destination, and at connection level, i.e., for each TCP connection. The technique uses different models to evaluate flows belonging to different protocols. For a TCP flow, it uses the packet ratio of the flow to determine if the flow is an attack. Whenever a flows packet ratio is greater than the threshold, D-WARD drops packets of the flow. Due to the connection level packet counts it maintains, D-WARD is able to selectively drop packets of the flow and thus penalizes only errant connections of the flow. D-WARD measures responsiveness to packet drops to determine if the flow is compliant with the TCP specification. Upon determination of a noncompliant flow, D-WARD limits the rate of the flow. D-WARD uses similar models for non-TCP protocols, such as ICMP and Domain Name System (DNS) traffic. D-WARD implements models for different applications that use UDP and applies those models on UDP flows to evaluate if the flows are legitimate. For other UDP flows which do not have a built-in application model or the application model cannot be determined, it applies rate limits to the flows.
D-WARD affords two configurations to handle detection in multi-gateway networks. In a first implementation, as shown in FIG. 2A, D-WARD capable routers are deployed at all gateways 212, 214 and these routers periodically exchange information over link 213 before flows and connections are classified. In a second implementation, shown in FIG. 2B, D-WARD capable routers 220, 222 and 224 are deployed within the source network at connection points between stub sub-networks and the rest of the source network behind gateways 216 and 218. In effect, each stub sub-network is treated as an independent stub domain.
D-WARD stores packet rate at per-destination and per-connection granularity. If attack packets are not spoofed, D-WARD can distinguish between legitimate traffic and attack traffic and selectively drop only attack packets. However, if attack packets are spoofed using other addresses in the domain, D-WARD may not correctly distinguish between attack and legitimate traffic. D-WARD maintains the flow and connection information in fixed size hash tables. This protects the D-WARD system from memory overflow and having to reinitialize memory. However, D-WARD still requires periodic checking of entries in the table to clear stale information, such as the state of inactive flows. Also, since D-WARD maintains per-flow and per-connection information, an attacker can exhaust D-WARD's memory resources by generating flows to arbitrary destinations and connections to arbitrary ports. D-WARD attempts to overcome such a situation by deleting records corresponding to flows that sent few packets and bytes when the data structures are 90% full. An attacker can use this mechanism to sneak its attack packets past the D-WARD system.
D-WARD cannot detect attacks directed against entire subnets. If several attackers participate in an attack, each attacker can send attack packets at a low rate and yet the attack would still be successful against D-WARD. If an attacker has multiple addresses to use in an attack, it can decrease the attack rate to individual addresses accordingly. Since D-WARD does not combine the analysis of different addresses in a subnet and since it uses hash tables of limited size, it can miss one or more flows belonging to the subnet attack and is then unable to prevent the attack from succeeding.
Given the shortcomings of the prior art, the need has been felt for a scalable DoS detection system that is deployable at a stub domain and that is robust against attacks directed to individual hosts as well as entire subnets.